Problém ôsmich dám.

©Ľudovít Lačný, M.R.Štefánika 26/19, 96501 Žiar nad Hronom, SLOVAKIA
Probléma ôsmich dám bol nastolený pred 153 rokmi a znel: Rozmiestnite na šachovnici 8 dám tak, aby žiadna nenapádala inú. Jedno z možných zovšeobecnení problému je: Rozmiestnite n dám na šachovnici n x n tak, aby žiadna nenapádala inú a najdite počet riešení. Výlučne o tomto type zovšeobecnenia problému sa bude v ďaľšom pojednávať, hoci použitú metódu možno využiť aj v iných typoch zovšeobecnenia.

 Na klasickom probléme ôsmich dám, tak ako bol nastolený pred vyše 150 rokmi, si možno otestovať aj IQ. Ak sa vám podarí v priebehu pätnástich minút nájsť jedno z 92 možných rriešení (ale bezchybné riešenie), tak môžete byť so svojím IQ z oblasti kombinačných schopností veľmi spokojní. Ešte aj tridsať minút možno považovať za dobrý výsledok. V inom prípade si treba zlepšiť  kombinačné schponosti pomocou hier s kombinačným zameraním.    
Bez pomoci počítača sa spomenutý zovšeobecnený problém podarilo vyriešiť až po šachovnicu 12x12, s pomocou počítača až po rozmer šachovnice 24x24. K tomuto vrcholnému výkonu však bolo treba použiť viac paralených procesorov a dní času. Ako  som zistil, mnohé pokusy nájsť s použitím matematických metód počet riešení ani pre klasickú šachovnicu 8 x 8 neboli úspešné. Viac o tomto pozri v linku: história problému.
V nasledujúcom chcem ukázať cestu ako možno počet riešení pre menšie rozmery šachovnce vypočítať a možno s využitím kolektívneho prístupu dosiahnuť najdenie počtu riešení aj pre vysoké hodnoty rozmerov šachovnice. Celý princip spočíva v rozdelení výpočtu na viacero fáz. Očakávam, že sa najdú spolupracovníci a možno aj sponzori, ktorí podporia tento obťažný zámer zrealizovať. Teraz už priamo k veci. Najprv treba definovať isté pojmy, aby sme si rozumeli.
Definície:
ROZMIESTNENIE je akékoľvek rozmiestnenie n dám na šachovnici n x n tak, že na každom stlci a rade sa nachádza  jedna dáma. Počet všetkých takýchto rozmiestnení na šachovnici n x n je n! (n-faktoriál).
RIEŠENIE je také ROZMIESTNENIE, že na každej diagonále leží jedna alebo žiadna dáma.
STRET vznikne, ak niekoľko dám leží na tej istej diagonále alebo diagonálach.
n-STRET znamená, že práve n dám je v STRETe a že každá z týchto dám je stretmi spojená s každou dámou stretu na jednej alebo viacerých diagonálach. n-STRET je v šachovom zmysle jednofarebný. Takýto n-STRET nazvime JEDNODUCHÝ STRET. Poznámka: 1-stret znamená, že nedochádza k stretu. Ak všetky dámy tvoria 1-srety je  ROZMIESTNENIE RIEŠENÍM.
n,m,…,z-STRET označuje zložený stret, ktorý pozostáva z n-STRETu, m-STRETu až z-STRETu pri čom žiadna dáma i-STRETu neleží na diagonále (diagonálach), na ktorých ležia dámy ostatných stretov. Aj keď možno každý stret znázorniť na šachovnici, budem v daľšom texte používať grafické znázornenie, ktoré vznikne otočením stretu o 45 stupňov v smere chodu hodín, čo podstatne zjednoduší a zprehľadní znázorňovanie. Tento prechod je ozrejmený v nasledujúcich príkladoch grafických znázornení stretov. .

Všetky strety tvoria množinu stretov. Z tejto množiny možno vytvoriť podmnožiny podobných stretov. Do podmnožiny podobných stretov patria strety, ktorých grafické znázornenie redukciou spojovníkov na jeden, vhodným otočením alebo/aj preklopením vznikne totožné grafické znázornenie. Ponechaný spojovník ukazuje len na existenciu väzby, pri čom vzdialenosť dám je irelevantná.. Takto vzniknutý graf charakterizuje podmnožinu podobných stretov a v daľšom budeme celú takúto podmnožinu nazývať  STRET...
Príklady: V rade 1 sú dva podobné strety a ich možný charakteristický stret. V rade 2a a 2b sa ukazuje, že charakteristický stret nič nehovorí o vzdialenosti dám. Aj keď v grafe 2b majú logicky červené dámy od seba inú vzdialenosť ako modré na tvar grafu to nevplýva. Dôležitá je len neprítomnosť spojovníka. 
V rade 3 je ukážka redukcie trochu zložitejšieho stretu .

Ešte raz zdôraznujem, že v dalšom texte STRETom budeme nazývat podmnožinu podobných STRETov.  Grafické znázornenie charakteristického môže byť rôzne, čo je dané možnosťou otáčania a preklápania, musí však byť z grafu jasné, o aký STRET sa jedná. Grafické znázornenie je vhodné pre svoju názornosť a pokým niet adekvátnej číselnej interpretácie budem ho používať.

Princip matematického riešenia zovšeobecneného problému ôsmich dám .

Ako už bolo uvedené, počet všetkých možných ROZMIESTNENí pre šachovnicu nxn je n! (n-faktoriál). Ak od tejto hodnoty odpočítame všetky STRETy, zostanú nám len riešenia. Prvé priblíženie riešenia možno získať tak, že od všetkých ROZMIESTNENí sa odpočítajú všetky ROZMIESTNENIA, kde sa vyskytuje aspoň jeden 2-STRET. Počet takýchto rozmiestnení sa získa násobením počtu týchto rozmiestnení  hodnotou (n - 2)!, lebo ešte na n - 2 ostávajúcich stlpcoch možno dámy rozmiestnit ako na šachovnici (n - 2)x(n -2). Pri tejto oprave sa zrejme odpočítalo viac rozmiestnení, než bolo treba. Ak bol v rozmiestnení napríklad prvok 3-STRETu O-O-O, tak odpočítanie sa vykonalo 3krát namiesto jednoho Preto treba vykonať nasledovnú korekciu: Treba pripočítat (lebo sa koriguje odpočítanie) 2krát počet prvkov tohoto 3-STRETu násobených (n-3)!. 2krát preto, lebo jedno odpočítanie musí zostať.Že sa 2-STRET O-O nachádza v 3-STRETe 3krát možno ľahko ukázať: Očíslujeme dámy 3-STRETu 123, potom spomínané 2-STRETy tvoria dámy 12 13 23.

 V rozmiestneniach sa však vyskytli aj prvky 3-STRETu tvaru "L", v ktorom sa prvky 2-STRETu nachádzajú 2krát a korekčný faktor teda bude 1. Aj keď sa týmto vyčerpali všetky 3-STRETy, korekcia na tejto úrovni ešte neskončila, lebo mohli vzniknúť rozmiestnenia s výskytom 2,2-STRETu. V tomto sa 2-STRET nachádza 2krát, teda korekcia bude mat hodnotu 1 a počet prvkov 2,2-STRETu sa bude násobiť (n - 4)!, lebo len toľko stĺpcov ostalo voľných. Týmto sa táto druhá úroveň uzatvára a nasleduje tretia, kde sa korekcie odpočítávajú pre 4-STRETy a 2,3-STRETy. Takto sa postupuje až po najvyššiu možnú úroveň. Uvedená metóda v podstate využíva v  kombinačnej matematike užívanú met´édu "zahrnutia a vylúčenia". 
Číslo, ktoré predstavuje korekciu nazvime korekčný faktor. Význam pojmu úroveň vyplýva z kontextu. Platí, že úroveň n-STRETu je n. Úroven zloženého STRETu sa rovná súčtu zložiek minus počet zložiek plus 1. Napríklad úroveň 2,4,7-STRETu je: 2+4+7-3+1=11. Z uvedeného postupu výpočtu vyplýva, že treba riešiť dve úlohy:

Ad 1:Vypočítat korekčné faktory.
Ad 2: Zistit počet prvkov STRETov.

Výpočet korekčného faktora

Aby výpočet korekčných faktorov bol ešte názornejší a mohla sa aspoň trochu preukázať platnosť dôležitých vzťahov prikladám nasledujúcu tabuľku:

   

V 1. stlpci je poradie riadku, v 2. znamienko úrovne, v 3. graf  STRETu, vo 4. je jednička ako doplňujúca hodnota (ukazuje. že jeden STRET sa musí zachovať),v 5.stlci 2.riadok je korekčný faktor, označený ako aj všetky ostatné červene. V stlpci pod korekčným faktorom sú čísla udávajúce koľkokrát sa STRET , ktrorého faktor je červene označený nachádza v STRETe príslušného riadku. Keď sa potom vypočítávajú korekčné faktory, treba čísla v stlpci vynásobiť červeným číslom uvedeným na vrchu stĺpca. Zlúčením takto získaných čísel dostaneme hodnotu korekčného faktora. Názorne pre 12.riadok:
1 - 4*1 + 1*2 + 0*1 + 3*1 = 2
Predbežné poznatky z tabuľky: Riadok 7. a 8. ako aj riadky 9. a 10. sú číselne zhodné, čo v týchto prípadoch nie je náhoda. V ďaľšom sa týmto budeme zaoberať podrobne Neskoršie si ukážeme, že platí: Korekčný faktor ZLOŽENÉHO STRETu sa rovná súčinu korekčných faktorov jednotlivých STRETov. Dokazovaním tejto vety sa budem zaoberať neskoršie.

 Pri vypočítávaní korekčných faktorov možno postupovať i "diferenčnou" metódou. Metóda je založená na tom, že ak ku grafu pridáme bod, prejdeme o jeden stupeň na vyššiu úroveň a potom stačí počítať len s podgrafmi, ktoré pribudli pridaním bodu. Pri tom treba zohľadniť zmenu znamienka. Príklad na využitie je v linku diferenciálna metóda.
 Pred ďalšími úvahami o korekčných faktoroch  treba aspoň čiastočne overiť správnosť uvedenej metódy získania  počtu riešení. Toto je urobené až po šachovnicu 6x6 v linku overenie metódy

Všeobecné úvahy o korekčných faktoroch.

Z predchádzajúcich úvah vyplynulo, že existuje metóda na výpočet korekčného faktora pre ľubovoľný STRET. Metóda však vyžaduje,  aby sa pri výpočte nevynechal žiadny STRET nižšej úrovne, čo nie je jednoducho realizovateľníá úloha ani s pomocou počítača. Zistil som však prekvapujúcu skutočnosť, že existujú  všeobecné vzorce pre výpočet korekčného faktora. Napred niekoľko definícií.

V stretoch existujú dámiy, ktoré ležia len na jednej diagonále a dámy ležiace na dvoch diagonálach. Posledne menované dámy nazvime spoločné dámy. Spoločné dámy môžu vytvárať strety spoločných dám. Množinu STRETov, ktoré majú rovnaký stret spoločných dám, nazvime ROD STRETov a prvok tejto množiny, ktorý pozostáva len zo spoločných dám RODIČ. Podmnožinu RODu STRETov, kde na príslušných radoch a stĺpcoch je rovnaký počet dám nazvime RODINa STRETov. Všetko bude zrejmejšie z nasledujúcich grafov STRETov, kde plné krúžky  predstavujú  spoločné dámy. V prvom rade sú tri prvky množiny RODINa STRETov. V druhom rade sú prvky RODu STRETov. Posledný graf predstavuje RODIČa. . Čísla nad jednotlivými radmi a stĺpcami grafu udávajú počet dám (spoločných i osamelých) v danom rade (stĺpci) minus 1. (Odpočítanie jednotky sa ukáže výhodným pre použitie vzorcov, ktoré budú uvedené v ďaľšom texte.

Zo vzorcov vyplýva, že prvky RODINy STRETov majú rovnaký korekčný faktor. To je zrejmé z toho, že do vzorcov sa dosadzujú totožné čísla..Pre RODIČov platí analogická veta ako pre STRETy: Pre RODINu RODIČov platí ten istý vzorec. Analógická veta pre STRETy je: RODINa STRETov má ten istý korekčný faktor.

Zo štruktúry prvých šiestich vzorcov sa dá pomocou analógie ľahko nájsť vzorec pre akéhokoľvek RODIČa analogickej štruktúry.Aj vo vzorcoch pre RODIČov zložitejších štruktúr možno nájsť isté zákonitosti, ale všeobecnú metódu tvorby vzorcov ešte nevidím. Korešpodencia medzi grafmi a vzorcami je veľmi zaujímavá ako ostatne i celá problematika  štruktúry korekčných faktorov. Očakávam, že sa najdú spolupracovnici a možno aj sponzori, ktorí podporia tento zaujímavý problém hlbšie riešiť. Zdá sa, že pri riešení treba využiť i teóriu grafov. Pre záujemcov pripájam

kde sú i zložitejšie štruktúry RODIČov. Nie je ich však dostatok pre všeobecnejšie výsledky, lebo môj počítač nestačí rýchlosťou.

V priebehu úvah sa ukázalo, že výpočet korekčného faktora a počtu stretov si vyžaduje riešiť problém usporiadania množiny STRETov. Vyriešením tejto úlohy je cesta výpočtu RIEˇŠENí pomocou počítača otvorená. Výhodou takéhoto postupu je, že ho možno riešiť po častiach. Zároveň možno použiť uvedené a v budúcnosti najdené vzorce pre korekčné faktory a vzorece pre počet prvkov STRETov. S posledne uvedeným problémom sa hodlám zaoberať v ďaľšom.

Počet prvkov STRETu.

 Zisťovanie počtu prvkov STRETu je podstatne náročnejšie než výpočet korekčného faktora. Toto súvisí s tým, že na rozdiel od výpočtu korekčného faktora,  treba hladať pre každý STRET osobitný vzorec, ktorý možno vôbec neexistuje. Existuje  tu však vždy možnosť zisťovať počty STRETov pomocou počítača.

Nájsť všeobecné vzorce je úloha veľmi náročná. Avšak i tu existuje veľmi povzbudivá nádej. Pre najjednoduchšiu RODINu STRETov (zatiaľ pre časť) existuje zaujímavý vzorec

 

Majme neúplnú rodinu stretov tvaru::

 

Ak S je rozmer štvorcovej šachovnice,  A,B počty dám podľa obrázku a P je počet stretov, potom platí:

 

P/k = å å( kk(S-i-2A-B+1,1).kk(S-i+j-2A-B+1,1).kk(i-j+A+B-2,B-1).kk(j,A-1).kk(i-2j+2A+B-3,0) +

      +  kk(S-i-2B-A+1,1).kk(S-i+j-2B-A+1,1).kk(i-j+A+B-2,A-1).kk(j,B-1).kk(i-2j+2B+A-3,0)),

 

pri čom sa sumovanie "i" aj "j" robí od 0 po "S" a pre A = B  je k = 4, pri A <> B je k = 8.

  . Funkcia kk(a.b) vo vzorci je kombinačný koeficient, ktorý sa pre kladné a nulové "a" zhoduje s binomickým koeficientom, ale pre záporné "a", sa rovná nule. Teda, ak "n!" znamená "n" faktoriál, platí:

             kk(a,b) = a! / (b!.(a - b)!),  ak a<0  alebo  b<0  tak kk(a,b) = 0

a tiež

             kk(a,0) = 1,  ak a >=  0.

 

Toto ukazuje na známy, ale nie samozrejmý fakt , že 0!  = 1.

       Uvedený vzorec pre počet stretov možno napísať i v iných formách:

 

P/k = å å kk(S-i-2j-3,1)kk(S-i-j-2,1)(kk(j,B-1)kk(i+j-B+1,A-1)+kk(j,A-1)kk(i+j-A+1,B-1))

 

       alebo vo forme:

 

P/k  = å åkk(j\2-i-j+S,1)kk(S-j+1,1)(kk(j\2-i-2,B-1)kk((j+1)\2+i-B-1,A-1)+ kk(j\2-i-2,A-1)kk((j+1)\2+i-A-1,B-1))

 

za tých istých podmienok pre sumovanie ako v prvom vzorci. symbol "\" predstavuje celočíselné delenie (delenie bez zbytku), napríklad 7\3  = 2.

     Nie je vôbec jednoduché nájsť zaiste existujúce transformácie medzi týmito vzorcami. Vzorce boli najdené vždy inou metódou prístupu k hladaniu vzorcov.

     Ďaľším cieľom je násť vzorec pre úplnú pertraktovanú RODINu STRETov. Čiastočné riešenie pre túto RODINU mám.

     Je načase uviesť moju predstavu o ďaľšom pláne postupu. Moja predstava je nasledovná:

     1.  Nájsť metódu pre tvorbu množiny RODIČov.

     2.  Doplniť výpočty riešení pre väčšie šachovnice (minimálne po 8x8).

     3.  Hladať vzorce pre počet stretov RODIČov.

     Prvé dve úlohy vyžadujú len čas. Tretia úloha je možno vo všeobecnejšom poňatí neriešiteľná. Vyriešením úlohy číslo 1 je možné pomocou pčítača nájsť riešenia i pre podstatne väčšie šachovnice.

     Kto sa podujme na spoluprácu?